package com.sxkiler.demo.easy;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import java.util.*;
import com.sxkiler.demo.model.*;

/**
check-if-n-and-its-double-exist=检查整数及其两倍数是否存在
<p>给你一个整数数组&nbsp;<code>arr</code>，请你检查是否存在两个整数&nbsp;<code>N</code> 和 <code>M</code>，满足&nbsp;<code>N</code>&nbsp;是&nbsp;<code>M</code>&nbsp;的两倍（即，<code>N = 2 * M</code>）。</p>

<p>更正式地，检查是否存在两个下标&nbsp;<code>i</code> 和 <code>j</code> 满足：</p>

<ul>
	<li><code>i != j</code></li>
	<li><code>0 &lt;= i, j &lt; arr.length</code></li>
	<li><code>arr[i] == 2 * arr[j]</code></li>
</ul>

<p>&nbsp;</p>

<p><strong>示例 1：</strong></p>

<pre><strong>输入：</strong>arr = [10,2,5,3]
<strong>输出：</strong>true
<strong>解释：</strong>N<code> = 10</code> 是 M<code> = 5 的两倍</code>，即 <code>10 = 2 * 5 。</code>
</pre>

<p><strong>示例 2：</strong></p>

<pre><strong>输入：</strong>arr = [7,1,14,11]
<strong>输出：</strong>true
<strong>解释：</strong>N<code> = 14</code> 是 M<code> = 7 的两倍</code>，即 <code>14 = 2 * 7 </code>。
</pre>

<p><strong>示例 3：</strong></p>

<pre><strong>输入：</strong>arr = [3,1,7,11]
<strong>输出：</strong>false
<strong>解释：</strong>在该情况下不存在 N 和 M 满足 N = 2 * M 。
</pre>

<p>&nbsp;</p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>2 &lt;= arr.length &lt;= 500</code></li>
	<li><code>-10^3 &lt;= arr[i] &lt;= 10^3</code></li>
</ul>
 方法一：暴力法
 直接遍历所有的数字对，判断一个数字是否是另一个数字的两倍。注意要用乘法判断，除法判断会有除零的问题。
 复杂度分析：
 时间复杂度：O(n^2)
 空间复杂度：O(1)
 方法二：排序 + 双指针
 先对所有数字进行排序。然后维护两个指针：指针 p 遍历数字 x，指针 q 寻找 2x。
 复杂度分析：
 时间复杂度：O(nlogn)
 排序的时间复杂度为 O(nlogn)，两次指针遍历的过程时间复杂度为 O(n)，综合起来，复杂度为 O(nlogn)。
 空间复杂度：O(n)
 Python 的 sort 函数空间复杂度为 O(n)，双指针遍历的空间复杂度为 O(1)，综合起来，复杂度为 O(n)。
 方法三：哈希表
 先将所有数字存入哈希表，再遍历所有的数字 x，判断 2x 是否在哈希表中。
 复杂度分析：
 时间复杂度：O(n)
 哈希表的查询时间复杂度为 O(1)，查询次数为 O(n)，综合起来，时间复杂度为 O(n)。
 空间复杂度：O(n)
 哈希表最多需要存储 n 个元素。


 */
public class checkIfExist {
    

    class Solution {
        public boolean checkIfExist(Integer[] arr) {
            Set set = new HashSet();
            int j = 0;
            for(int i:arr){
                if(i==0){
                    if(j++>1)return true;
                    continue;
                }
                set.add(Integer.valueOf(i));
            }
            for(Integer i:arr){
                if(set.contains(Integer.valueOf(2*i)))return true;
            }
            return false;
        }
    }

    @Test
    public void test(){
        Solution solution = new Solution();
        Integer [] param0 = new Integer[]{10,2,5,3};
        Assertions.assertEquals(solution.checkIfExist(param0),true);
    }
}

